import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhourh on 2018/9/12.
 *
 * 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

 示例:
 输入: S = "a1b2"
 输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

 输入: S = "3z4"
 输出: ["3z4", "3Z4"]

 输入: S = "12345"
 输出: ["12345"]
 注意：

 S 的长度不超过12。
 S 仅由数字和字母组成。
 */
public class LetterCasePermutation {

    public static void main(String[] args) {
        System.out.println(new LetterCasePermutation().letterCasePermutation2("a1b2"));
        System.out.println(new LetterCasePermutation().letterCasePermutation2("3z4"));
        System.out.println(new LetterCasePermutation().letterCasePermutation2("12345"));
    }

    public List<String> letterCasePermutation2(String S) {
        List<String> list = new ArrayList<>();
        letterCasePermutation(list, S.toCharArray(), 0);
        return list;
    }

    public List<String> letterCasePermutation(List<String> list, char[] array, int index) {
        if (index == array.length) {
            list.add(new String(array));
        } else {
            if (Character.isLetter(array[index])) {
                array[index] = Character.toUpperCase(array[index]);
                letterCasePermutation(list, array, index + 1);
                array[index] = Character.toLowerCase(array[index]);
                letterCasePermutation(list, array, index + 1);
            } else {
                letterCasePermutation(list, array, index + 1);
            }
        }

        return list;
    }

    public List<String> letterCasePermutation(String S) {
        List<String> cases = new ArrayList<>();
        if (S == null) {
            return cases;
        }

        if (S.isEmpty()) {
            cases.add(S);
            return cases;
        }

        if (S.length() == 1 && S.charAt(0) >= '0' && S.charAt(0) <= '9') {
            cases.add(S);
        } else if (S.length() == 1 && ((S.charAt(0) >= 'A' && S.charAt(0) <= 'Z')
                || ((S.charAt(0) >= 'a' && S.charAt(0) <= 'z')))) {
            cases.add(S.toLowerCase());
            cases.add(S.toUpperCase());
        } else if (S.length() > 1 && S.charAt(0) >= '0' && S.charAt(0) <= '9'){
            List<String> otherCases = letterCasePermutation(S.substring(1));
            for (String otherCase : otherCases) {
                cases.add(S.substring(0, 1) + otherCase);
            }
        } else if (S.length() > 1 && ((S.charAt(0) >= 'A' && S.charAt(0) <= 'Z')
                || ((S.charAt(0) >= 'a' && S.charAt(0) <= 'z')))) {
            List<String> otherCases = letterCasePermutation(S.substring(1));
            for (String otherCase : otherCases) {
                cases.add(S.substring(0, 1).toLowerCase() + otherCase);
                cases.add(S.substring(0, 1).toUpperCase() + otherCase);
            }
        }

        return cases;
    }
}
